package com.hyc.algorithm.tree;

import com.hyc.algorithm.Node.TreeNode;

import java.util.Arrays;

/**
 * @projectName: DataStructure
 * @package: com.hyc.algorithm.tree
 * @className: InAndAfterReductionTree
 * @author: 冷环渊 doomwatcher
 * @description: TODO
 * @date: 2022/4/4 16:41
 * @version: 1.0
 */
public class InAndAfterReductionTree {
    public static void main(String[] args) {
        int[] after = new int[]{4, 5, 2, 6, 3, 1};
        int[] mid = new int[]{4, 2, 5, 1, 3, 6};
        TreeNode result = buildTree(mid, after);
        System.out.println(result);
    }

    public static TreeNode buildTree(int[] zhong, int[] hou) {
        if (hou == null || zhong == null || hou.length == 0 || zhong.length == 0 || hou.length != zhong.length) {
            return null;
        }
        //   从后序遍历中找到根节点
        TreeNode root = new TreeNode(hou[hou.length - 1]);
        int rootindex = 0;
        int rootval = root.val;
        //从中序数组中找到 root
        for (int i = 0; i < zhong.length; i++) {
            if (zhong[i] == rootval) {
                rootindex = i;
            }
        }
        //找到左子树的中序和后序
        int[] leftZhong = Arrays.copyOfRange(zhong, 0, rootindex);
        int[] leftHou = Arrays.copyOfRange(hou, 0, rootindex);
        //找到右子树的中序和后序
        int[] rightZhong = Arrays.copyOfRange(zhong, rootindex + 1, zhong.length);
        int[] rightHou = Arrays.copyOfRange(hou, rootindex, hou.length - 1);
        //    递归构建左右子树
        TreeNode left = buildTree(leftZhong, leftHou);
        TreeNode right = buildTree(rightZhong, rightHou);
        //    给根节点添加左右子树
        root.left = left;
        root.right = right;
        return root;
    }
}
